package algorithm.heap;

import util.BaseUtil;

import java.util.Arrays;

/**
 * 二叉堆练习
 * @Author Antony
 * @Since 2018/7/5 17:13
 */
public class BinaryHeap {

    public static void main(String[] args) {
//        int[] array_1 = BaseUtil.randomIntArray(20,200);
//        int[] minHeap = minTopHeap(array_1);
//        int[] kthMinHeap = kthMinHeap(array_1,10);
//        System.out.println(Arrays.toString(minHeap));
//        System.out.println(Arrays.toString(kthMinHeap));

        int[] t1 = new int[]{3,2,1,5,6,4};
        int k = 2;
        int result = findKthLargest(t1, k);
    }


    public static int findKthLargest(int[] array, int k) {
        int[] heap = new int[k];
        int hole,tmp,parIndex;
        for(int i=0; i<k; i++){
            hole = i;
            tmp = array[i];
            parIndex = (i-1)/2;
            while(hole > 0 && heap[parIndex] > tmp){
                heap[hole] = heap[parIndex];
                hole = parIndex;
                parIndex = (parIndex-1)/2;
            }
            heap[hole] = tmp;
        }

        for(int i=k; i<array.length; i++){
            if(array[i] > heap[0]){
                minHeapDown(heap, array[i]);
            }
        }
        System.out.println(Arrays.toString(heap));

        return heap[0];
    }

    // 将数组变成小顶堆
    public static int[] minTopHeap(int[] array){
        int[] heap = new int[array.length];
        int tmp,holeIndex,parentIndex;
        for(int i=0; i<heap.length; i++){
            tmp = array[i];
            holeIndex = i;
            parentIndex = (i-1)/2;
            while(holeIndex >0 && tmp < heap[parentIndex]){
                heap[holeIndex] = heap[parentIndex];
                holeIndex = parentIndex;
                parentIndex = (parentIndex-1)/2;
            }
            heap[holeIndex] = tmp;
        }
        return heap;
    }


    // 创建k大二叉堆,并不是标准二叉堆，子节点左右大小没有序
    public static int[] kthMinHeap(int[] array, int k){
        int[] heap = new int[k];
        int hole,tmp,parIndex;
        for(int i=0; i<k; i++){
            hole = i;
            tmp = array[i];
            parIndex = (i-1)/2;
            while(hole > 0 && heap[parIndex] > tmp){
                heap[hole] = heap[parIndex];
                hole = parIndex;
                parIndex = (parIndex-1)/2;
            }
            heap[hole] = tmp;
        }
        return heap;
    }

    // 小顶堆,堆顶值下沉
    public static void minHeapDown(int[] heap, int val){
        int parent = 0;
        int lChild, rChild, minIndex, tmpVal;
        while(parent < heap.length){
            lChild = parent*2+1;
            rChild = parent*2+2;
            minIndex = parent;
            tmpVal = val;

            // 由于是先比左边，所以左边如果符合条件，就赋值 tmpVal=heap[lChild]
            if(lChild < heap.length && tmpVal > heap[lChild]){
                minIndex = lChild;
                tmpVal = heap[lChild];
            }

            if(rChild < heap.length && tmpVal > heap[rChild]){
                minIndex = rChild;
            }

            if(minIndex == parent){
                break;
            }else{
                heap[parent] = heap[minIndex];
                parent = minIndex;
            }
        }
        heap[parent] = val;
    }
}
